package com.rom.sort;

import com.rom.Utils.Random;

import java.util.Arrays;
import java.util.Date;

public class InsertSort {

    public static void main(String[] args) {

//        int arr[] = {3,2,1,4,5};
        int arr[] = new int[300000];
        System.out.println(new Date());
        for (int i = 0; i < 300000; i++) {
            arr[i] = Random.random80000();
        }
        insertSort(arr);
//        System.out.println(Arrays.toString(arr));
        System.out.println(new Date());
    }

    //插入排序
    public static  void insertSort(int[] arr){

        int index = 0;
        //无序列表从第一项开始
        for (int i = 1; i < arr.length; i++) {
            //插入的值
            int insertVal = arr[i];
            int insertIndex = i-1;
            while ( insertIndex>=0 && insertVal < arr[insertIndex]){
                index++;
                arr[insertIndex + 1] = arr[insertIndex];
                arr[insertIndex] = insertVal;
                insertIndex--;
            }
        }
        System.out.println(index);
    }
}
